package com.simon.study.algorithm.leetcode;

/**
 * <p>
 *
 * @author simon
 */
public class MinSumSquareDiff02333 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{18,4,8,19,13,8};
        int[] nums2 = new int[]{18,11,8,2,13,15};
        int k1 = 16, k2 = 8;

        minSumSquareDiff(nums1, nums2, k1, k2);
    }

    public static long minSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2) {
        int[] diff = new int[nums1.length];

        for(int i=0; i<diff.length; i++){
            diff[i] = Math.abs( nums1[i] - nums2[i] );
        }

        int ds = diff.length;
        mergeSort(diff, 0, ds-1);


        consum(diff, k1);
        consum(diff, k2);

        int sum = 0;
        for(int i=0; i<ds; i++){
            sum = sum + diff[i]*diff[i];
        }
        return sum;
    }

    public static void consum(int[] diff, int k1){
        int ds = diff.length;
        while (k1 != 0 && diff[ds-1] >0){
            for(int i=ds-1; i>0; i--){
                if( diff[i] < diff[i-1] ){
                    swap(diff, i, i-1);
                }else{
                    break;
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j){
        if( i == j ){ return; }

        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static void mergeSort(int[] arr, int as, int ae){
        if(as >= ae){ return; }

        int mid = as + ((ae-as)/2);

        mergeSort(arr, as, mid);
        mergeSort(arr, mid+1, ae);
        merge(arr, as, ae, mid);
    }

    public static void merge(int[] arr, int as, int ae, int mid){
        int lp = as, mp = mid+1, idx=0;

        int[] dup = new int[ae-as+1];

        while (lp <= mid && mp <= ae){
            dup[idx++] = arr[lp] < arr[mp] ? arr[lp++] : arr[mp++];
        }

        while (lp <= mid){ dup[idx++] = arr[lp++]; }
        while (mp <= ae ){ dup[idx++] = arr[mp++]; }

        for (int i = 0; i < dup.length; i++) { arr[as+i] = dup[i]; }
    }
}
